package com.black.play.entity;

import com.black.play.util.ArrayUtil;

import java.util.*;

public class SudokuGenerator
{
    private static final int SIZE = 9; // 数独大小
    private static final int SUBGRID_SIZE = 3; // 子网格大小
    private static final Random RANDOM = new Random(); // 随机数生成器

    /**
     * 生成一个完整的数独棋盘。
     * <p>
     * 此方法通过调用solveSudoku方法来填充一个初始为空的数独棋盘，从而创建一个完整的数独谜题。
     * 它首先初始化一个大小为SIZE*SIZE的二维数组作为数独棋盘的底层数据结构，然后通过解决数独问题的方式
     * 填充这个数组。最后，它使用这个填充好的数组创建并返回一个SudokuBoard对象。
     *
     * @return SudokuBoard 一个填充好的数独棋盘对象。
     */
    public static SudokuBoard generateCompleteSudoku()
    {
        int[][] board = new int[SIZE][SIZE];
        // 生成一个完整的数独解
        solveSudoku(board);
        // 返回解决后的数独棋盘作为SudokuBoard对象
        return new SudokuBoard(board);
    }

    /**
     * 使用递归回溯算法解决数独问题。
     * 该方法尝试在数独板上的每个空格填入合适的数字，以满足数独的解条件。
     * 如果找到解，返回true；如果没有找到解，返回false。
     *
     * @param board 数独板，表示为一个二维数组，0 表示空格。
     * @return 如果找到解则返回true，否则返回false。
     */
    public static boolean solveSudoku(int[][] board)
    {
        // 遍历数独板的每一行和每一列
        for (int row = 0; row < SIZE; row++)
        {
            for (int col = 0; col < SIZE; col++)
            {
                // 当前位置为0表示这是一个空格，需要填入数字
                if (board[row][col] == 0)
                {
                    // 获取候选数字列表
                    int[] candidates = generateCandidates(board, row, col);
                    // 尝试填入每个候选数字
                    for (int num : candidates)
                    {
                        // 填入数字并递归尝试解决剩余的空格
                        board[row][col] = num;
                        if (solveSudoku(board))
                        {
                            // 如果递归成功找到解，返回true
                            return true;
                        }
                        // 如果递归失败，撤销填入的数字，回溯到上一状态
                        board[row][col] = 0;
                    }
                    // 如果所有候选数字都无法解决问题，返回false
                    return false;
                }
            }
        }
        // 如果遍历完整个数独板没有找到空格，说明已经解决完毕，返回true
        return true;
    }

    /**
     * 生成指定位置的候选数字列表。
     * 候选数字是指在当前单元格中可能填写的数字，不会与同一行、同一列或同一子网格内的已填数字重复。
     *
     * @param board 数独棋盘
     * @param row   当前单元格的行索引
     * @param col   当前单元格的列索引
     * @return 当前单元格的候选数字数组
     */
    private static int[] generateCandidates(int[][] board, int row, int col)
    {
        // used数组用于标记1到9的数字是否已被使用
        boolean[] used = new boolean[SIZE + 1];
        // count用于记录当前行、列和子网格中已使用的数字数量
        int count = 0;
        // 遍历当前行和列，标记已使用的数字
        for (int i = 0; i < SIZE; i++)
        {
            if (board[row][i] != 0 && !used[board[row][i]])
            {
                used[board[row][i]] = true;
                count++;
            }
            if (board[i][col] != 0 && !used[board[i][col]])
            {
                used[board[i][col]] = true;
                count++;
            }
        }

        // 计算当前单元格所属的子网格的起始行和列索引
        int startRow = row - row % SUBGRID_SIZE;
        int startCol = col - col % SUBGRID_SIZE;
        // 遍历子网格，标记已使用的数字
        for (int i = 0; i < SUBGRID_SIZE; i++)
        {
            for (int j = 0; j < SUBGRID_SIZE; j++)
            {
                if (board[startRow + i][startCol + j] != 0 && !used[board[startRow + i][startCol + j]])
                {
                    used[board[startRow + i][startCol + j]] = true;
                    count++;
                }
            }
        }
        // 初始化候选数字数组，长度为可用数字的数量（9-count）
        int[] candidates = new int[SIZE - count];
        int index = 0;
        // 将未被使用的数字添加到候选数字数组中
        for (int i = 1; i <= SIZE; i++)
        {
            if (!used[i])
            {
                candidates[index++] = i;
            }
        }
        // 对候选数字数组进行随机排序，以增加解谜的随机性
        ArrayUtil.shuffle(candidates);
        return candidates;
    }

    /**
     * 从数独棋盘中随机移除数字，以创建数独谜题。
     * 移除数字的过程中确保数独棋盘保持唯一解的特性。
     *
     * @param board    二维数组表示的数独棋盘。
     * @param numHoles 需要移除的数字数量。
     */
    public static void removeNumbersFromBoard(int[][] board, int numHoles)
    {
        // 已经移除的数字数量
        int holesMade = 0;
        // 当移除的数字数量达到要求前，持续进行移除操作
        while (holesMade < numHoles)
        {
            // 随机生成待移除数字的行和列位置
            int row = RANDOM.nextInt(SIZE);
            int col = RANDOM.nextInt(SIZE);
            // 如果当前位置有数字，则尝试移除
            if (board[row][col] != 0)
            {
                // 备份当前位置的数字，以便后续恢复
                int backup = board[row][col];
                board[row][col] = 0;

                // 检查当前状态下的数独谜题是否有唯一解
                int[][] boardCopy = new int[SIZE][SIZE];
                for (int i = 0; i < SIZE; i++)
                {
                    System.arraycopy(board[i], 0, boardCopy[i], 0, SIZE);
                }
                // 如果移除后的棋盘没有唯一解，则恢复之前移除的数字
                if (!hasUniqueSolution(boardCopy))
                {
                    board[row][col] = backup; // 恢复挖去的数字
                }
                else
                {
                    // 如果移除后的棋盘没有唯一解，则恢复之前移除的数字
                    holesMade++;
                }
            }
        }
    }

    /**
     * 检查数独谜题是否有唯一解。
     * 通过创建数独板的一个副本，并计算该副本的解的数量来检查唯一性。
     * 如果解的数量为1，则数独谜题有唯一解。
     *
     * @param board 二维数组表示的数独板，其中0表示空白位置。
     * @return 如果数独谜题有唯一解返回true，否则返回false。
     */
    private static boolean hasUniqueSolution(int[][] board)
    {
        // 创建一个与原数独板相同大小的副本
        int[][] boardCopy = new int[SIZE][SIZE];
        // 将原数独板复制到副本中，保持初始状态不变
        for (int i = 0; i < SIZE; i++)
        {
            System.arraycopy(board[i], 0, boardCopy[i], 0, SIZE);
        }
        // 计算副本数独板的解的数量
        // 如果解的数量为1，则原数独谜题有唯一解
        return countSolutions(boardCopy) == 1;
    }

    /**
     * 计算数独谜题的解决方案数量。
     * 通过调用solveSudoku尝试解决数独板，并通过solutionCount数组跟踪解决方案的数量。
     * 此方法是设计为静态方法，因为它不需要实例化对象来计算解决方案数量。
     *
     * @param board 一个二维数组，表示待解决的数独谜题。
     * @return 返回数独谜题的解决方案数量。
     */
    private static int countSolutions(int[][] board)
    {
        // 初始化一个数组来存储解决方案的数量，之所以使用数组而不是基本类型，是为了在solveSudoku中能够通过引用传递并更新计数。
        int[] solutionCount = {0};
        // 调用solveSudoku方法尝试解决数独，并通过solutionCount来收集解决方案的数量。
        solveSudoku(board, solutionCount);
        // 返回解决方案的数量。
        return solutionCount[0];
    }

    /**
     * 解决数独问题的递归函数。
     * 通过尝试在空格中填充数字，寻找所有可能的解决方案。
     *
     * @param board         数独棋盘，一个二维数组，表示当前的数独状态。
     * @param solutionCount 一个整数数组，用于统计找到的解决方案数量。
     */
    private static void solveSudoku(int[][] board, int[] solutionCount)
    {
        // 遍历数独棋盘的每一行和每一列
        for (int row = 0; row < SIZE; row++)
        {
            for (int col = 0; col < SIZE; col++)
            {
                // 当前位置为0表示这是一个空格，需要填充数字
                if (board[row][col] == 0)
                {
                    // 生成当前位置可能的候选数字
                    int[] candidates = generateCandidates(board, row, col);
                    // 尝试每个候选数字
                    for (int num : candidates)
                    {
                        // 填充候选数字，并检查是否完成数独解决方案
                        board[row][col] = num;
                        if (solveSudoku(board))
                        {
                            solutionCount[0]++;
                        }
                        // 回溯，撤销填充的数字，尝试下一个候选数字
                        board[row][col] = 0; // 回溯
                    }
                    // 找到解决方案后，返回上一级，继续处理其他空格
                    return;
                }
            }
        }
        // 如果遍历完整个棋盘未返回，说明所有空格都已填满，无需进一步处理
    }
}
